# 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
#
#  示例 1:
# 输入: s = "abcabcbb"
# 输出: 3
# 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
#
#  示例 2:
# 输入: s = "bbbbb"
# 输出: 1
# 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
#
#  示例 3:
# 输入: s = "pwwkew"
# 输出: 3
# 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
#     请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
#
#
#  Related Topics 哈希表 字符串 滑动窗口 👍 10111 👎 0


class Solution:
    def lengthOfLongestSubstring2(self, s: str) -> int:
        """
        双指针 + set  => 滑动窗口
        遍历字符串，通过双指针循环定位子串 右指针在哈希表中是否存在：
            否，记录到set，移动右指针，计算长度，比较并保留最大值；
            是，删除set中左指针元素，移动左指针，重复检查右指针元素是否还存在；
        """
        s1 = sorted(s)
        s2 = sorted(s)
        print(sorted(s))
        print(s1 == s2)
        strLen = len(s)
        if strLen <= 1:
            return strLen
        left, right = 0, 0
        mySet = set()  # set 用于记录每个字符是否出现过
        res = 0
        while right < strLen:
            if not s[right] in mySet:
                mySet.add(s[right])
                res = max(res, right - left + 1)
                right += 1
            else:
                mySet.discard(s[left])
                left += 1
        return res

    def lengthOfLongestSubstring1(self, s: str) -> int:
        """
        解法一：
        双指针，每次移动指针时判断字符是否在子串里面
        """

        def is_contain(i: int, j: int, ch: str) -> bool:
            for t in s[i:j]:
                if t == ch:
                    return True
            return False

        left, right, str_len = 0, 0, len(s)
        if str_len <= 1:
            return str_len
        res = 1
        while left <= right:
            # 三种写法都可以，这种最高效
            if right < str_len and s[right] not in list(s[left:right]):
                # if right < str_len and s[right] not in s[left:right]:
                # if right < str_len and not is_contain(left, right, s[right]):
                res = max(res, right - left)
                right += 1
            else:
                res = max(res, right - left)
                left += 1
        return res

    def lengthOfLongestSubstring(self, s: str) -> int:
        return self.lengthOfLongestSubstring2(s)


if __name__ == '__main__':
    s = "abcabcbb"
    print(Solution().lengthOfLongestSubstring(s))
